// problem : http://www.topcoder.com/stat?c=problem_statement&pm=10835

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std; 

class KingdomXCitiesandVillagesAnother 
{
public: 
    int findroot(int n, const vector<int>& un)
    {
        if (un[n] == -1) return -1; 
        
    	while (un[n] != -1 && n != un[n])
    	{
    	    n = un[n];
    	}
    	return n;
    }

    bool samecomp(int n1, int n2, const vector<int>& un)
    {
        int a = findroot(n1, un); 
        int b = findroot(n2, un); 
        if (a == -1 || b == -1) return false;
        if (a == b) return true;
    	return false;
    }
    
    void connect(int n1, int n2, vector<int>& un)
    {
    	//cout << "before" << endl; 
    	//cout << "connect" << " " << n1 << " " << n2 << endl; 
    	//for (int i = 0; i < un.size(); ++i)
    	//	cout << un[i] << " "; 
    	//cout << endl; 
    	
		int root1 = findroot(n1, un); 
		int root2 = findroot(n2, un); 
		
		if (root1 == -1 && root2 == -1)
		{
		    un[n1] = min(n1, n2); 
		    un[n2] = min(n1, n2); 
		}
		
		else if (root1 == -1)
		{
		    un[n1] = min(root2, n1); 
		    un[root2] = min(root2, n1);
		}
		
		else if (root2 == -1)
		{
		    un[n2] = min(root1, n2); 
		    un[root1] = min(root1, n2);
		}
		else 
		{
			un[root1] = un[root2] = min(root1, root2);
		}
		//cout << endl; 
    	//cout << "after" << endl; 
    	//for (int i = 0; i < un.size(); ++i)
    	//	cout << un[i] << " "; 
    	//cout << endl; 
    }
    
    double dist(double a1, double b1, double a2, double b2)
    {
        double dx = a1 - a2; 
        double dy = b1 - b2; 
        
        return sqrt(dx * dx + dy * dy);
    }
    double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) 
    {
        int matsize = villageX.size() + 1; 
        vector<vector< double > > mat(matsize, vector<double>(matsize, 0.0)); 
        
        for (int i = 0; i < mat.size(); ++i)
        {
        	for (int j = 0; j < i; ++j)
        	{
				if (i == mat.size() - 1) 
				{
				    double mindist = 2e8;
					for (int k = 0; k < cityX.size(); ++k) 
					{
					    mindist = min(mindist, dist(villageX[j], villageY[j], cityX[k], cityY[k]));
					}
					mat[i][j] = mindist;
				}
				else mat[i][j] = dist(villageX[i], villageY[i], villageX[j], villageY[j]);
        	}
        }
        
        vector<pair< double, pair<int, int> > > edges; 
        
        for (int i = 0; i < mat.size(); ++i)
        	for (int j = 0; j < i; ++j)
        	{
        		pair<double, pair<int, int> > cur(mat[i][j], make_pair(i, j));
        		vector<pair<double, pair<int, int> > > ::iterator it = upper_bound(edges.begin(), edges.end(), cur);
        		edges.insert(it, cur);
        	}
        
        vector<int> un(mat.size(), -1); 
        int addededges = 0; 
        double res = 0.0;
		for (int i = 0; i < edges.size(); ++i)
		{
			int n1 = edges[i].second.first; 
			int n2 = edges[i].second.second; 
			
			if (!samecomp(n1, n2, un))
			{
			    res += edges[i].first; 
			    connect(n1, n2, un);
			    addededges ++;
			}
			if (addededges == villageX.size()) break; 
		}
		return res; 
    }
};
